home *** CD-ROM | disk | FTP | other *** search
/ The Hacker Chronicles - A…the Computer Underground / The Hacker Chronicles - A Tour of the Computer Underground (P-80 Systems).iso / miscpub1 / tj3_6.txt < prev    next >
Text File  |  1992-09-26  |  29KB  |  654 lines

  1. The LOD/H Technical Journal, Issue #3: File 06 of 11
  2.  
  3.               |||||||||||||||||||||||||||||||||||||||||||||||||||
  4. +-+-+-+-+-+-+/                                                   \+-+-+-+-+-+-+
  5.  \  L  \        Secure Data Encryption with Cellular Automatons        /  L  /
  6.    \  O  \                                                           /  O  /
  7.      \  D  \                          by                           /  D  /
  8.        +-+-+-+                                                   +-+-+-+
  9.          \  L  \                  The Mentor                   /  L  /
  10.            \  O  \                                           /  O  /
  11.              \  H  \    A Legion of Doom Presentation!     /  H  /              
  12.                +-+-+-+                                   +-+-+-+
  13.                 \_\_\_\_________________________________/_/_/_/
  14.  
  15.  
  16.      One of the key issues that concerns anyone who has sensitive or illegal
  17. information on their computer system is preventing unauthorized access to this
  18. information.  Even if you hit a key that deletes everything on the hard disk
  19. when you see that four-door sedan pull up in the driveway, any idiot with
  20. Norton's Utilities (IBM) or Copy II+ (Apple) can recover anything that's on 
  21. your drive with minimal effort.  A delete command only changes a flag in the
  22. VTOC (volume table of contents), it doesn't actually *remove* the file from
  23. your system.
  24.      There are two methods to ensure that your data can't be read by a sector
  25. editor or recovered by NU.  The first is to overwrite everything with a NULL
  26. (FF) or anything else for that matter.  I've seen one batch file that does a
  27. global delete, creates a file that says 'EAT HOT DEATH', and then begins
  28. copying it until disk space is full.  Unfortunately, you can't always guarantee
  29. that you will be able to get to your computer before someone else does.
  30.       The second method is to encrypt your data.  Most people have visions of
  31. data encryption being some sort of arcane process akin to summoning demons or
  32. talking with Dead Cow Cult members (two closely related process- es.)  In
  33. practice, it isn't that difficult.  This file is intended to show some very
  34. short programs that will encrypt data beyond the ability of any- thing short of
  35. a dedicated mainframe to crack.  
  36.  
  37.      How to use:  The code examples I provide will be in MicroSoft's 
  38. AmigaBASIC.  It is fairly generic and you should be able to convert it over to 
  39. IBM, //e,c,gs, Mac, ST, C64, or any flavor of mainframe you like.  For those of
  40. you setting up systems on Packet-Switched Networks (such as the LOD/H system
  41. one of our members is implementing) data encryption should be considered
  42. absolutely necessary to maintain security.
  43.       The terseness of the routines make them easy to insert in a bulletin
  44. board also, although conversion into C or Assembly would be necessary for
  45. decent speed.
  46.  
  47.       Intro to Cryptography:  Long before computers were around, there was a
  48. need for data security.  Everyone used lemon juice as 'invisible ink' when they
  49. were a kid, heating it over a candle to bring it out.  And everyone has seen
  50. the substitution code where "A" = 1, B = "2", "Z" = 26, etc...  
  51.       The easiest form of encryption involves a variation of the previous.  
  52. First of all, don't think of A = 1 as a substitution, think of it as a 
  53. remapping.  Let's say we have a language made up of the five vowels, and we
  54. wanted to remap them to the numbers 1-5.  Our map would look like this:
  55. "AEIOU12345" and our mapping function would be f(c) = POSITION(c) + x where c =
  56. the letter to map and x is the key (in this case 5.)  So every time we needed
  57. to encrypt a letter, we would take its position in the map, add 5 to it, and
  58. come up with the character to substitute.  For the entire alphabet, the mapping
  59. function would be f(c) = POS(c) + 26 for the map "A..Z,1..26".
  60.        Your map should be composed of all the characters that will be used for
  61. encryption.  In a text only encrypter, this will consist of all the printable
  62. characters your machine can use.  The same method can be used to encrypt binary
  63. files, but it's not as clear as text only for a teaching example.
  64.        The problem with this simple form of encryption is that your average C64
  65. could crack it in a matter of minutes.  Enter into the next level of
  66. cryptography, random numbers.
  67.        During World War II the Allied Forces created a system to generate
  68. random electric noise, recorded this noise onto a wax cylinder, and scram- bled
  69. radio transmissions by mixing the seemingly random noise with the voice
  70. transmission.  The soldiers in the field needed an imprint of the same cylinder
  71. to be able to understand the message.  Think of the wax cy- linder as a
  72. 'filter' for the crypted message.
  73.        A random number generator can be easily used to encrypt data providing
  74. you realize the following-  a random number generator on a computer is not
  75. really random.  If you initialize the generator with the same seed value on two
  76. seperate occasions, it will return the same sequence of psuedo- random
  77. numbers.  Most BASIC's use the RANDOMIZE <seed> command to start the generator
  78. off.  If you leave off the seed, they get a seed from the system clock or some
  79. other fairly random source, providing a much truer random selection.  But by
  80. declaring the seed yourself, you can be sure that you will be able to reference
  81. this same string of numbers, a string that is very hard to figure out without
  82. the key (seed.)  
  83.         Program Listing 1 is an example of a BASIC encrypt/decrypt system that
  84. uses the built-in random number generator include on the machine (or language
  85. implementation.)
  86.  
  87. Program Listing 1
  88. -----------------
  89.  
  90. REM ************************************************************************
  91. REM 
  92. REM  Ok, this is an example of very basic encryption.  It takes the input
  93. REM  string and the input key and processes them using the machine's built
  94. REM  in random number generator.  This version is written in AmigaBASIC 1.2.
  95. REM  It can be compacted quite a bit by writting it in C, but it's an easy
  96. REM  algorithm to crack.
  97. REM
  98. REM ************************************************************************
  99.  
  100. INPUT "String to be encoded"; C$
  101. INPUT "Key Please! ";K
  102.  
  103.  
  104. REM ************************************************************************
  105. REM
  106. REM  When you use the RANDOMIZE command, it seeds the random number gener-
  107. REM  ator with the key K.  *EVERY* time you seed the generator with the same
  108. REM  value, you will get the same sequence of psuedo-random numbers.  Since
  109. REM  the built in random-number generator uses a linear algorithm to gener-
  110. REM  ate the sequence, it's easy (relatively) to crack.
  111. REM
  112. REM ************************************************************************
  113.  
  114. RANDOMIZE K
  115.  
  116. REM ************************************************************************
  117. REM
  118. REM  The only difference between encoding and decoding is which way you 
  119. REM  move in your Q$ array space.  Encoding takes the original and shifts
  120. REM  to the right, decoding takes the codes value and shifts to the left.
  121. REM
  122. REM ************************************************************************
  123.  
  124. REREAD:
  125.   INPUT "Encode or Decode ? ";A$
  126.   A$=LEFT$(A$,1)
  127.   IF A$="E" OR A$="e" THEN
  128.     A=1
  129.     GOTO HEAD
  130.   END IF
  131.   IF A$="D" OR A$="d" THEN
  132.      A=-1 
  133.   ELSE
  134.      GOTO REREAD
  135.   END IF
  136.  
  137. REM ************************************************************************
  138. REM
  139. REM  Q$ contains all the characters that can be encoded.  Every encoded 
  140. REM  character will be mapped to a character in this array.  I haven't 
  141. REM  included any non-standard characters, so you will have to customize
  142. REM  it to your particular keyboard/system.  I've included an error check
  143. REM  that will abort the encryption if it encounters a character that isn't
  144. REM  in Q$.  I have to use the STRING$ command to insert the spacebar and
  145. REM  the quote into the string.  It could also be done with a ASC(##) in
  146. REM  many basics.  You could expand this to include any non-printable 
  147. REM  characters you'd like so you could do non-text files.
  148. REM
  149. REM ************************************************************************
  150.  
  151. HEAD:
  152.   SPACE = 32
  153.   QUOTE = 34
  154.   Q$="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
  155.   Q$=Q$+"1234567890!@#$%^&*()-=_+[]{};:'.,<>/?\|`~"
  156.   Q$=Q$+STRING$(1,SPACE)+STRING$(1,QUOTE)
  157.   QSIZ = LEN(Q$)
  158.  
  159. REM ************************************************************************
  160. REM
  161. REM  This is the main loop.  L = length of the string to encrypt.  In this
  162. REM  example, I am only encrypting a single string.  Most people who will 
  163. REM  actually use this will change the FOR loop to run until an EOF is 
  164. REM  encountered in the input file.  Since the syntax for that will vary
  165. REM  widely from system to system, I'll leave it out.
  166. REM
  167. REM ************************************************************************
  168.  
  169. L=LEN(C$)
  170. FOR I = 1 TO L
  171.  
  172. REM /* Finds the character I in the input string */
  173.   X$ = MID$(C$,I,1)
  174.   
  175. REM /* Finds the integer location of the character in Q$ 
  176. REM    returns variable POZ */  
  177.   GOSUB LOKPOZ
  178.                                                                          
  179. REM /* RND returns a random # between 0 and 1.  Multiply it by the
  180. REM    size of array Q$ and you get the number of positions to move
  181. REM    when encoding or decoding. */
  182.   POZMV = (RND * QSIZ)
  183.  
  184. REM /* If you are encoding, you will shift to the right using addition.
  185. REM    you take the modula base QSIZ to keep the new character within
  186. REM    the bounds of Q$. */  
  187.   IF A = 1 THEN
  188.     NUPOZ = (POZ + POZMV) MOD QSIZ
  189.   ELSE
  190. REM /* Otherwise, you subtract, which takes a bit more math to keep
  191. REM    up with.  Once you have the distance to shift, you must 
  192. REM    convert it to a positive integer and then subtract two to
  193. REM    account for the head & tail of the array. */  
  194.     NUPOZ = (POZ - POZMV) MOD QSIZ
  195.     NUPOZ = NUPOZ -2
  196.     IF NUPOZ < 1 THEN
  197.       NUPOZ = QSIZ - ABS(NUPOZ)
  198.     END IF
  199.   END IF
  200.   
  201. REM /* Now you assign the new character in array Q$ to Y$, and append
  202. REM    it to your converted string */  
  203.   IF NUPOZ < 1 THEN
  204.     NUPOZ = QSIZ - ABS(NUPOZ)
  205.   END IF
  206.   Y$ = MID$(Q$,NUPOZ,1)
  207.   D$ = D$ + Y$
  208. NEXT I
  209.  
  210. PRINT  "Original = ";C$
  211. PRINT  "Modified = ";D$
  212. END
  213.  
  214. REM /* This finds character X$ in array Q$ and returns an integer
  215. REM    value of the location.  Called from the main loop. */
  216. LOKPOZ:
  217.   FOUND = 0
  218.   POZ = 1
  219.   TOP:
  220.     IF FOUND = 1 THEN 
  221.       RETURN
  222.     ELSE
  223.       TMP$ = MID$(Q$,POZ,1)
  224.       IF X$ = TMP$ THEN
  225.         FOUND = 1
  226.       END IF
  227.       POZ = POZ + 1
  228.       IF POZ > QSIZ THEN 
  229.         PRINT  "Error: Character '";X$"' not in array Q."
  230.         END
  231.       END IF
  232.     END IF
  233.   GOTO TOP        
  234.  
  235. REM **********************************************************************
  236.  
  237. End of Program Listing 1
  238.  
  239.         This method, while extremely simple, tight, and fast, is not fool-
  240. proof.  Most computers use the following algorithm for generating pseudo-
  241. random number sequences: x(t+1) = ax(t) + b
  242.         x(t+1) = next random number
  243.         x(t) = previous random number
  244.         a & b are constants that will cause a fairly even distribution
  245.  
  246.         For example, if you were using a three-bit system (8 possible postive
  247. integers) you might make a = 3 & b = 7 (there's a reason behind using prime
  248. numbers that is beyond the scope of this file.)  If you seed the argument with
  249. RANDOMIZE 5 you would get the following:
  250. First x: x = 3*5 + 7 | Since we're restricting ourselves to three bits, and
  251.          22 won't fit in three bits, we'd need to perform a modula 8 on the
  252.          number. (Modulo divides x by eight and keeps the remainder as the
  253.          new value of x.)  So  MOD(22,8) is equal to 6 (16 + 6 = 22).
  254.          
  255.          Ok, let's do some simple mapping using our vowel set and the above
  256. three-bit random number generator.  Let's say that the message reads "AAEOU"
  257. Our first random number was 6.  Our map looks like "AEIOU12345".  POS(A) + 6
  258. gives us 2 as the character.  
  259. Second x: x = 3*6 + 7 | MOD (25,8) = 1 | POS(A) + 1 gives us E.
  260. Third  x: x = 3*1 + 7 | MOD (10,8) = 2 | POS(E) + 2 gives us O.
  261. Fourth x: x = 3*2 + 7 | MOD (13,8) = 5 | POS(O) + 5 gives us 4.
  262. Fifth  x: x = 3*5 + 7 | MOD (22,8) = 6 | POS(U) + 6 wraps around the map to A.
  263.  
  264.          So our original "AAEOU" is crytped into "2E04A".  This may at first
  265. seem difficult to crack since 'A' mapped into a '2' on one pass and an 'E' on
  266. the other, thus preventing a freuquency analysis from breaking the code.
  267.         Unfortunately, if someone knows the random number algorithm, they can
  268. easily hack out the key.  Since most of the people using this will be using it
  269. on a pc, it would be trivial to get another pc to hack it out.  And even if you
  270. protect your random number algorithm, it is still a straight linear algebra
  271. problem that an AT could work on over a weekend and probably figure it out,
  272. especially if there is a fairly small map to work with.
  273.          
  274.           Solution: What we need to do is combine the random mapping with a
  275. random number generator that is tougher to figure out.  Enter cellular 
  276. automatons.
  277.           CA's were first invented in the 1940's when John von Neumann (he of
  278. the famous bottleneck) started to explore the mathmatic implications of very
  279. simple machines.  CA's are made of geometric patterns of cells that change
  280. their state at each tick of a clock according to a fixed rule.  Early work
  281. provided automatons that could imitate a basic computer.  Since the CA's are
  282. inherently parallel (the entire geometry is updated each clock tick) and easy
  283. to put on a chip, there is speculation that the next generation of parallel
  284. processing computers will use CA's as a base rather than the Turing machine
  285. model.
  286.            You have probably seen a CA at work and not realized it if you've
  287. ever seen the computer graphic simulation 'LIFE' developed by John Conway at
  288. MIT to model real organisms.  The rule for automaton reproduction was incr-
  289. edibly simple: If a cell has two or three neighbors, no change in the cell.
  290. Fewer or more neighbors, it starves or is overcrowded to death, and repro-
  291. duction occurs when a blank space has exactly three neighbors.
  292.         Using these simple rules, incredibly complex patterns can be produced.
  293. Anything that can produce complex and varied results from a small algorithm is
  294. a good target for a random number application.  Enter Steven Wolfram from the
  295. Institute of Advanced Studies in Princeton, NJ.
  296.         Wolfram has been doing research on one-dimensional cellular machines,
  297. which have the advantage of being able to work with both todays machines and
  298. future parallel machines.  Wolfram has developed an automaton that is a one
  299. dimensional circular array modified by the rule:
  300.        
  301.         a(x,t) = a(x-1,t-1) XOR (a(x,t-1) OR a(x+1,t-1)) MOD k
  302.        
  303.         Where x is the position in the array and t is the time,
  304.         k is the number of available characters (k = LEN(Q$)),
  305.         and a is the one-dimensional array.                        
  306.  
  307.         This rule has several interesting properties.  The problem we had with
  308. linear algorithms was that simple algebra could be used to analyze the
  309. evolution of the algorithm (the patterns produced.)  All that you have to do is
  310. figure out how *one* cell evolves, then apply that pattern across the entire
  311. array.  In the above case, there is no way of analyzing the array at time t
  312. without loading the initial conditions and running the whole thing.  
  313.         The second thing to note is that there are k to the power of w (where w
  314. is the width (number of cells) in array a) possible states the machine can be
  315. in, and not all of these states have a predecessor that generates it.  These
  316. states are called 'Garden of Eden' states, and can only occur if they are set
  317. as an ititial condition.  
  318.          As a result, this rule is neither a one-to-one mathmatical mapping,
  319. nor is it and onto mapping of the set of arrays into itself.  In laymans'
  320. terms, this means that for any given array state it is impossible to tell what
  321. (if any) previous state generated it by mere pattern analysis.
  322.          While this isn't a file on breaking codes- about the only way to crack
  323. this one that's been discovered is to load *every* k**w state into memory and
  324. page through them searching for a pattern.  This method can be defeated easily
  325. by setting w to more than 30 cells (assuming k=256, all the ASCII characters.) 
  326. If you are using my array Q$, you might want to set w to 40 or more.  Since 256
  327. to the 30th power is about a zillion bits, roughly equal to the largest memory
  328. bank in existence, there isn't much chance of anyone breaking it.  For the
  329. truly paranoid, set w to 50 and sleep easy at night.
  330.  
  331.          Anyway, back to the algorithm...
  332.  
  333.         Each of the cells is filled on one of the k integers from 0 to k-1,
  334. giving each cell k possible states.  Wolfram found that the string of bits
  335. occupying the 0 position (a(0,1), a(0,2), a(0,3)...) forms a random sequence
  336. that passes all statistical tests, sometimes with better results than standard
  337. DES algorithms.
  338.         Let's break this down and see what it's doing.  First of all, we will
  339. need two arrays.  Each array is set up thus:
  340.  
  341.                         Array for Time One                 
  342.         |------|       |------|       |------|      |------|
  343.   |---->|a(0,1)|------>|a(1,1)|------>|a(2,1)|----->|a(3,1)|-----|
  344.   |     |------|       |------|       |------|      |------|     |         
  345.   |--------------------------------------------------------------|
  346.  
  347.                         Array for Time Two              
  348.         |------|       |------|       |------|      |------|
  349.   |---->|a(0,2)|------>|a(1,2)|------>|a(2,2)|----->|a(3,2)|-----|
  350.   |     |------|       |------|       |------|      |------|     |         
  351.   |--------------------------------------------------------------|
  352.  
  353.         The reason we need two arrays is so you can update the array without
  354. destroying anything in it.  In other words, you start out with array 1 active,
  355. then you update the array into array 2 and change the active array to 2.  On
  356. the next clock tick you will update the active array (now 2) into the inactive
  357. one (now 1) and set the active array back to 1.  You keep swapping like this. 
  358. Logically, you only have one array- the active one.
  359.          To initialize the array, the ASCII values of each character in the key
  360. are plugged into the first LEN(KEY$) spaces in the array.  If you want to use a
  361. short key, modify the code to fill the *entire* array with values of the key
  362. (keep repeating a loop from 1 to W pulling characters out of K).  Since the key
  363. can be anything printable, use something 10-20 characters long that you can
  364. remember- "HACK TO LIVE, LIVE TO HACK" is one of my favorites.  Anyway, if you
  365. use a short (less than 10) key in this program, the distri- bution will be
  366. skewed for the first W MOD LEN(KEY$) itereations of the automaton, but will
  367. smooth out nicely after that.
  368.           After the array is filled, it operates exactly like the first program
  369. *except* when it need a random number of positions to move.  Then it drops
  370. down, updates each cell in the automaton, and then reads the value in A(0,time)
  371. as the random number to shift by.
  372.           Let's look at the modified encryption code.
  373.  
  374. REM ************************************************************************
  375. REM
  376. REM  This is an modification of Program 1 that doesn't use a machine 
  377. REM  specific random number generator, but instead uses a cellular automaton
  378. REM  algorithm.  W is the width of the actual automaton.  A is dimensioned
  379. REM  at 32 to avoid having to reference element 0 of the array, which is
  380. REM  legal on some systems and illegal on the others.  This way it can
  381. REM  be implemented on anything.  Y is set for time 1, Y1 for time 2.  
  382. REM  These correspond to the second dimension in array A.
  383. REM
  384. REM ************************************************************************
  385.  
  386. W = 30
  387. DIM A(32,2)
  388. Y = 1
  389. Y1 = 2
  390.  
  391. REM ************************************************************************
  392. REM 
  393. REM  Once again, you can set this up to use files instead of strings. And
  394. REM  note that, unlike the first example, the key doesn't have to be
  395. REM  numeric.
  396. REM 
  397. REM ************************************************************************
  398.  
  399. INPUT "String to be encoded"; C$
  400. INPUT "Key Please! (Can be alpha-numeric) ";K$
  401.  
  402.  
  403. REM ************************************************************************
  404. REM
  405. REM  This is where K$ is broken down into a series of characters and their
  406. REM  ASCII value shoved sequentially into array A.  
  407. REM
  408. REM ************************************************************************
  409.  
  410. FOR I = 1 TO LEN(K$)
  411.   T$ = MID$(K$,I,1)
  412.   A(I,Y1) = ASC(T$)
  413. NEXT I  
  414.  
  415.  
  416. REM ************************************************************************
  417. REM
  418. REM  The only difference between encoding and decoding is which way you 
  419. REM  move in your Q$ array space.  Encoding takes the original and shifts
  420. REM  to the right, decoding takes the codes value and shifts to the left.
  421. REM
  422. REM ************************************************************************
  423.  
  424. REREAD:
  425.   INPUT "Encode or Decode ? ";A$
  426.   A$=LEFT$(A$,1)
  427.   IF A$="E" OR A$="e" THEN
  428.     A=1
  429.     GOTO HEAD
  430.   END IF
  431.   IF A$="D" OR A$="d" THEN
  432.      A=-1 
  433.   ELSE
  434.      GOTO REREAD
  435.   END IF
  436.  
  437. REM ************************************************************************
  438. REM
  439. REM  Q$ contains all the characters that can be encoded.  Every encoded 
  440. REM  character will be mapped to a character in this array.  I haven't 
  441. REM  included any non-standard characters, so you will have to customize
  442. REM  it to your particular keyboard/system.  I've included an error check
  443. REM  that will abort the encryption if it encounters a character that isn't
  444. REM  in Q$.  I have to use the STRING$ command to insert the spacebar and
  445. REM  the quote into the string.  It could also be done with a ASC(##) in
  446. REM  many basics.  You could expand this to include any non-printable 
  447. REM  characters you'd like so you could do non-text files.
  448. REM
  449. REM ************************************************************************
  450.  
  451. HEAD:
  452.   SPACE = 32
  453.   QUOTE = 34
  454.   Q$="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
  455.   Q$=Q$+"1234567890!@#$%^&*()-=_+[]{};:'.><,/?\|"
  456.   Q$=Q$+STRING$(1,SPACE)+STRING$(1,QUOTE)
  457.   QSIZ = LEN(Q$)
  458.  
  459.  
  460. REM ************************************************************************
  461. REM
  462. REM  This is the main loop.  L = length of the string to encrypt.  In this
  463. REM  example, I am only encrypting a single string.  Most people who will 
  464. REM  actually use this will change the FOR loop to run until an EOF is 
  465. REM  encountered in the input file.  Since the syntax for that will vary
  466. REM  widely from system to system, I'll leave it out.
  467. REM
  468. REM ************************************************************************
  469.  
  470. L=LEN(C$)
  471. FOR H = 1 TO L
  472.  
  473. REM /* Finds the character I in the input string */
  474.   X$ = MID$(C$,H,1)
  475.   
  476. REM /* Finds the integer location of the character in Q$ 
  477. REM    returns variable POZ */  
  478.   GOSUB LOKPOZ
  479.  
  480. REM /* CELLULAR updates the cells in the automaton, switches the active
  481. REM    time value, and returns X as the number of positions to shift. */
  482.   GOSUB CELLULAR
  483.   
  484. REM /* If you are encoding, you will shift to the right using addition.
  485. REM    you take the modula base QSIZ to keep the new character within
  486. REM    the bounds of Q$. */  
  487.   IF A = 1 THEN
  488.     NUPOZ = (POZ + X) MOD QSIZ
  489.   ELSE
  490.   
  491. REM /* Otherwise, you subtract, which takes a bit more math to keep
  492. REM    up with.  Once you have the distance to shift, you must 
  493. REM    convert it to a positive integer and then subtract two to
  494. REM    account for the head & tail of the array. */  
  495.     NUPOZ = (POZ - X) MOD QSIZ
  496.     NUPOZ = NUPOZ - 2
  497.       IF NUPOZ < 1 THEN
  498.         NUPOZ = QSIZ - ABS(NUPOZ)
  499.       END IF
  500.     END IF
  501.   
  502. REM /* Now you assign the new character in array Q$ to Y$, and append
  503. REM    it to your converted string */  
  504.   IF NUPOZ < 1 THEN
  505.     NUPOZ = QSIZ - ABS(NUPOZ)
  506.   END IF
  507.   Y$ = MID$(Q$,NUPOZ,1)
  508.   D$ = D$ + Y$
  509. NEXT H
  510.  
  511. PRINT  "Original = ";C$
  512. PRINT  "Modified = ";D$
  513. END
  514.  
  515. REM /* This finds character X$ in array Q$ and returns an integer
  516. REM    value of the location.  Called from the main loop. */
  517. LOKPOZ:
  518.   FOUND = 0
  519.   POZ = 1
  520.   TOP:
  521.     IF FOUND = 1 THEN 
  522.       RETURN
  523.     ELSE
  524.       TMP$ = MID$(Q$,POZ,1)
  525.       IF X$ = TMP$ THEN
  526.         FOUND = 1
  527.       END IF
  528.       POZ = POZ + 1
  529.       IF POZ > QSIZ THEN 
  530.         PRINT  "Error: Character '";X$"' not in array Q."
  531.         END
  532.       END IF
  533.     END IF
  534.   GOTO TOP      
  535.   
  536. REM ***********************************************************************
  537. REM  
  538. REM  This is the cellular automaton
  539. REM
  540. REM ***********************************************************************
  541.  
  542. CELLULAR:
  543.  
  544. REM /* Goes through the loop updating into the inactive time (1 or 2 dep-
  545. REM    ending on how Y and Y1 are assigned) */
  546.   FOR I = 1 TO W
  547.     A(I,Y) = A(I-1,Y1) XOR (A(I,Y1) OR A(I+1,Y1))
  548.   NEXT I
  549.  
  550. REM /* Updates the ends of the array (logical positions 0 and 31) that
  551. REM    are used in calculating other fields. */
  552.   A(0,Y) = A(W+1,Y1) XOR (A(0,Y1) OR A(1,Y1))
  553.   A(W+1,Y) = A(W,Y1) XOR (A(W+1,Y1) OR A(0,Y1))
  554.  
  555. REM /* Assigns the first cell to X as a random number */
  556.   X = A(1,Y)
  557.  
  558. REM /* Flips the active time */
  559.   TMP = Y
  560.   Y = Y1
  561.   Y1 = TMP
  562.  
  563. RETURN
  564.  
  565.          Ok, let's trace through a *small* example.  Assume our earlier
  566. map of "AEIOU12345" and an automaton of width 5.  For a key, we'll use
  567. "A15".
  568.  
  569. 1) Assign ASC(A) to a(1,1), ASC(1) to a(2,1), ASC(5) to a(3,1).
  570.    ("0" will represent an empty cell in this example.)
  571.    A(time 1) = 0 65 49 53 0 0 0
  572.    (Remember that an array of width 5 is going to have 7 actual elements)
  573.    
  574. 2) Now then, we want to encrypt the string "EE3"
  575.    First, we locate where E is in our map. LOKPOZ("E") = 2
  576.  
  577. 3) Now then, we update the automaton.
  578.    a(1,2) = 0 XOR (65 OR 49)
  579.    a(2,2) = 65 XOR (49 OR 53)
  580.    a(3,2) = 49 XOR (53 OR 0)
  581.    a(4,2) = 53 XOR (0 OR 0)
  582.    a(5,2) = 0 XOR (0 OR 0)
  583.    
  584.    Since this isn't a tutorial on binary numbers and boolean algebra, you'll
  585.    have to trust me on this one...
  586.    
  587.    a(1,2) = 113
  588.    a(2,2) = 116
  589.    a(3,2) = 4
  590.    a(4,2) = 53
  591.    a(5,2) = 0
  592.    
  593. 4) Now we update the ends.
  594.    a(0,2) = 0 XOR (0 OR 65)
  595.    a(6,2) = 0 XOR (0 OR 0)
  596.    
  597.    Again...
  598.    a(0,2) = 65
  599.    a(6,2) = 0
  600.    
  601. 5) Now we switch the active time from 1 to 2, and our new automaton is
  602.    a(time 2) = 65 113 116 4 53 0 0
  603.  
  604. 6) We then pull off a(1,2) as the number to shift by.
  605.  
  606. 7) Postion 2 + 113 (we're encoding, so we add) is 5 (modulo arithmatic.)
  607.  
  608. 8) "E" is encoded into "U".
  609.  
  610. 9) We repeat this two more times (you don't really want me to step through
  611.    it all, do you?) and end up with the encrypted version.
  612.    
  613.          Well, that's going to pretty much wrap this file up.  If you are
  614. interested in more files of this nature, let me know.  If you find this totally
  615. confusing, but want to learn more, call The Phoenix Project at 512/441-3088
  616. (300/1200/2400, 24 hours a day).  Our friendly and helpful LOD/H staff will be
  617. glad to assist you.  Other people who you might want to talk to about
  618. encryption include Dr. Cypher, Tuc, and Prime Suspect.
  619.          Also, if you are interested in seeing the above algorithm applied in
  620. other languages let me know.  If there's enough of a demand I'll release C,
  621. Modula-2, and ADA versions.
  622.  
  623.        This has been a Legion of Doom/Legion of Hackers presentation!
  624.  
  625.                               The Mentor
  626.                                  LOD/H
  627.                      
  628. *****************************************************************************
  629. References and Acknowledgments: 
  630.  
  631. "How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits";
  632. M. Blum & S. Micali; SIAM Journal of Computing, vol. 13, p. 850 (1984)
  633.  
  634. "Functions of Random Variables"; John Freund & Ronald Walpole;
  635. Mathmatical Statistics, 4th Edition; Prentice-Hall Inc., NJ; pp. 240-71
  636.  
  637. "Building an Encryption System"; Peter Wayner
  638. Computer Language, Vol. 4, Num. 12, p. 67 (Dec. 1987 Issue)
  639.  
  640. "Random Sequence Generation by Cellular Automata"; Institute for Advanced
  641. Study; Advances in Applied Mathmatics;
  642.  
  643. "Breaking Pseudo-Random Number Based Cryptographic Algorithms"; M. Vahle &
  644. L. Tolendino;  CRYPTOLOGIA, Oct 1982, p. 319
  645.  
  646. Also my thanks to: TUC, The Leftist, Prime Suspect, and Dr. Cypher, who all
  647.            contributed to this one way or another.
  648.  
  649. ***************************************************************************
  650.  
  651.  
  652. 
  653. Downloaded From P-80 International Information Systems 304-744-2253 12yrs+
  654.